#define _CRT_SECURE_NO_WARNINGS 1

struct ListNode {
	int val;
	struct ListNode *next;

}; 
struct ListNode* middleNode(ListNode* head)
{
	struct ListNode* fast, *slow;
	fast = head, slow = head;

	while (fast&&fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}

	return slow;
}

struct ListNode* reverselist(ListNode* head)
{
	struct ListNode* n1, *n2, *cur;
	n1 = head, n2 = NULL;
	while (n1)
	{
		cur = n1->next;
		n1->next = n2;
		n2 = n1;
		n1 = cur;
	}

	return n2;
}


	bool chkPalindrome(ListNode* A)
	{
		struct ListNode* mid = middleNode(A);
		struct ListNode* rlist = reverselist(mid);

		while (rlist)
		{
			if (A->val != rlist->val)
				return false;
			A = A->next;
			rlist = rlist->next;
		}

		return true;
	}
